import utils.TreeNode;

/**
 * @author ZCR
 * @create 2025/9/9 21:17
 */
public class Solution450 {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null) {
            return null;
        } else if (key < root.val) {
            root.left= deleteNode(root.left, key);
        } else if (key > root.val) {
            root.right= deleteNode(root.right, key);
        } else if (key == root.val) {
            if (root.left == null) {
                return root.right;
            }
            if (root.right == null) {
                return root.left;
            }
            TreeNode minNode = getMin(root.right);
            root.right = deleteNode(root.right, minNode.val);
            root.val = minNode.val;
        }
        return root;

    }
    public TreeNode getMin(TreeNode root) {
        TreeNode p = root;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }

    public static void main(String[] args) {
        Solution450 solution = new Solution450();
        TreeNode.show(solution.deleteNode(TreeNode.buildTree(new int[]{5,3,6,2,4,-1,7},-1), 3));
        TreeNode.show(solution.deleteNode(TreeNode.buildTree(new int[]{5,3,6,2,4,-1,7},-1), 0));

    }
}
